\documentclass[10pt,a4paper]{report}
\usepackage{a4wide}
\usepackage[portuges]{babel}
\usepackage[utf8]{inputenc}
% Title Page

\title{Relatório}


\author{João  Alturas nº. 6197}

\begin{document}
\maketitle

\begin{abstract}

Este trabalho tem por base a implementação de um algoritmo,denominado por A*, no âmbito da  disciplina de Estruturas de Dados e Algoritmos.

Com a implementação deste algoritmo pretende-se determinar o caminho  mais curto entre um ponto inicial A e um ponto final B.

O Algoritmo tem por base o estudo do funcionamento e da complexidade computacional, baseada em
dados recolhidos experimentalmente, do algoritmo de pesquisa heurística em grafos conhecidos por
A*.\\

\end{abstract}

\chapter{ Introdução}

\section{ Contextualização do trabalho}
	Este trabalho insere-se na avaliação da disciplina "Estruturas de Dados e Algoritmos", leccionada no 2º semestre, do 2º ano, da licenciatura em Engenharia Informática  da Escola Superior e Tecnologia de Beja do IPBeja do ano de 2013/2014.\\ 
	O trabalho surge na sequência do projecto de avaliação da disciplina de EDA.\\
	Este trabalho foi implementado na linguagem Java já abordada noutras disciplinas e das quais o docente permite que se  implemente o trabalho.\\
	 Estas linguagens caracterizam-se por assumirem em tempo de execução comportamentos comuns a outras linguagens , podem incluir  a extensão de outros programas por adição de novos  objectos.\\
	
	
\section{ Objectivos}
	
	Pretende-se com o referido trabalho implementar o algoritmo A*, o qual foi  programado no contexto da pesquisa de caminhos mais curtos, entre dois pontos de uma imagem digital em níveis de cinzento entre 0 e 255  .\\	
	Pretende-se que a aplicação seja capaz de realizar as seguintes tarefas:\\	
	
	Que se introduza conhecimento sobre o problema em causa o qual depende do nó origem para determinar os nós a visitar na iteração seguinte até atingir o próximo nó.\\ 
		
	 Também deve ser defenida a função de custo passado, que é a distância conhecida do nó de origem ao nó atual x,designada por g(x).\\
	
	Deverá ainda implementar a função de custo futuro, que é uma estimativa heurística admissível da distância de x ao objetivo, designada por h(x).\\
	
	No problema em causa, associado a cada ponto da imagem está a sua intensidade local, e a função de custo passada.
	Bem como a função  g(x) que  é a soma das intensidades locais por onde passou o caminho.\\
	
	Preve-se que o caminho futuro é a distância em linha reta de um ponto a outro ponto.\\
	
	 A função   f(x) é a soma das duas funções .\\
	 	  
		f(x) = g(x) + h(x) .\\		
	
	 Pretende-se ainda  que o trabalho  va ler os dados em formato de imagem e apresente o respectivo caminho desenhando uma linha, simulando o caminho, que vai do ponto de origem até ao ponto destino.\\
	 
	 Pretende-se ainda medir os tempos de execução e apresentar os respectivos resultados num gráfico extraindo-se daí conclusões.\\
	
	
\section{ Descrição da estrutura do relatório}
	
	Os algoritmos estão programados de acordo com o paradigma de programação consistente com a programação orientada por objetos , na linguagem java.\\
	
	 Os algoritmos foram implementados  sob a forma de classes e packages.\\
	
\section{ arquitetura do código}

O Código está estruturado numa package, que por sua vez contém  várias classes, metodos e funções e variaveis, como apresentado adiante.
	

\section{ Modulos}
Foram uilizadas as seguintes bibliotecas módulos.\\

	import javax.imageio.ImageIO;.\\
	import java.io.IOException;.\\
	import java.awt.image.BufferedImage;\\
	import java.io.BufferedWriter;\\
	import java.io.File;\\
	import java.io.FileWriter;\\
	import javax.swing.JFrame;\\	

\section{desempenho computacional teoricamente previsto de cada algoritmo }
	

\chapter{ Teoria}

\section{ Explicação teórica}
	
	Para organizar este trabalho debrucei-me sobre alguns  livros fornecidos pelo docente e também sobre alguns sites, nomeadamente Wikipédia Algoritmo A*.\\
	Comecei por visualizar num site a explicação do algoritmo Dijktra e o do caixeiro viajantee ainda alguns exemplos de algoritmos de NP.\\
	Alguns Problemas Dificeis Famosos.\\
	Caixeiro Viajante ("Traveling Salesman"): Dado um grafo pesado G.\\
	Fazendo busca em largura e profundidade.\\	
	 Problema Opt: Determinar o circuito de Hamilton de peso minimo.\\
	 Problema Dec: Para um inteiro k, haver  algum circuito de Hamilton em G, com peso  k?\\
	Aplicacoes: O caixeiro viajante pretende minimizar a distancia total percorrida para passar por todas as cidades que 		deve visitar. Mas tambem: circuito optimo, para recolha de lixo ou entrega de correio numa cidade . . .\\

	Acontece que  após a leitura da informação disponibilizada,  passo apresentar alguns excertos que entendi interessantes :\\
	Métodos Informados de Busca
	``Usam informações do domínio do problema para selecionar o melhor caminho até encontrar sua solução.\\
	Define-se uma função heurística h(n) que avalia o custo (ou distância) do caminho de um nó n até o
	estado final do problema (solução)''.\\

	Avalia-se o resultado da função heurística h(n), para decidir qual nó será expandido no próximo nível .\\
	
	Função Heurística.\\

	Deve ser sempre menor ou igual ao melhor valor possível.\\

	A função de custo nunca pode decrescer.\\

	Propriedades:\\

	h(n) = 0, n é o nó objetivo.\\

	h(n) > 0, a solução está em outro nó.\\

	h(n) tem valor infinito se é impossível atingir o estado final.\\
	
	Manhattan Distance.\\

	É a soma das distâncias entre as peças e suas respectivas posições.\\
	
	Algoritmo A*.\\

	Expandir o nó que pertence ao caminho com um menor custo associado.\\

	Função de avaliação: f(n) = g(n) + h(n), onde g(n) dá o valor do custo do caminho percorrido desde
	a raiz até o nó n.\\

	Tenta primeiro os nós com menor custo.\\

	Complexidade espacial exponencial.\\

	Encontra caminho optimo.\\
	
	Listas de nós Abertos e fechados.\\

	Inserção ordenada (abertos).\\

	Busca por estados já visitados.\\
	
	Ou seja começa no ponto de partida A e acrescente-o a uma "lista aberta" de pontos a serem considerados.\\
	 A lista aberta é como uma lista de compras.  A lista contém pontos que poderiam cair ao longo do caminho que  se pretende percorrer. Basicamente, esta é uma lista de pontos que precisam de ser verificadas. \\ 
	Seguidamente percorre todos os pontos  que podem ser passados  e que  sejam adjacentes ao ponto de partida, acrescentando-os de seguida  à lista aberta. Para cada um destes pontos e guarda o ponto A, como sendo o nó pai.\\
	 Este ponto pai é muito importante quando nós quisermos defenir o caminho. \\
	Seguidamente retira o ponto  A da lista aberta, e acrescenta-o  a uma lista fechada de pontos.\\
	Depois disto, nós escolhemos um dos pontos adjacentes na lista aberta e mais ou menos repetimos o processo anterior.\\
	
	A chave para determinar quais pontos devem ser  procurados e seguir  o caminho é a seguinte equação:\\

	f = g + h \\
	
	g = é o custo do movimento para se mover do ponto de início até ao próximo ponto.\\
	
	h = é o custo estimado do movimento para se deslocar daquele ponto A determinado até o destino final, ponto B.\\
	
	Para continuar a procura, escolhemos simplesmente o ponto que contém o valor mais baixo de todos .\\

  	   Retira-se da lista aberta e  acrescenta-se à lista fechada.\\

       Confire-se os pontos adjacentes. Ignorando os que estão na lista fechada ,  acrescentam-se os pontos à lista aberta, 
 eles já não estiverem na lista aberta. \\
     Se um ponto adjacente já estiver na lista aberta, confire para ver se este caminho para aquele ponto for melhor.\\ 
     Por  outras palavras, verifica se o G para aquele ponto é mais baixo, se nós usarmos o ponto atual para chegar lá.  Se 	não for, não faça nada.    
     Por outro lado, se o custo G do novo caminho é menor, troque o pai do quadrado adjacente para o quadrado selecionado.\\
      Finalmente, recalcule o F e G daquele ponto.\\
      
      Em termos gerais o algoritmo A * funcionará da seguinte forma:\\
      
      Adicione o ponto inicial à lista aberta.\\

      Procure o ponto que tenha o menor custo de F na lista aberta.\\

      Mova-o para a lista fechada.\\

      Utilizando uma grelha com 8 pontos adjacentes a este ponto corrente.\\

      Se estiver na lista fechada, ignore. Caso contrário faça o seguinte:\\

       Se não estiver na lista aberta, acrescente-o à lista aberta. Faça o ponto atual o pai deste nó.\\ 
       Guarde  os custos F, G, e H do ponto. \\

       Se já estiver na lista aberta, confira para ver se este caminh,o para aquele ponto é melhor, usando custo G como medida.\\
        Um valor G mais baixo mostra que este é um caminho melhor.\\
         Neste caso, mude o nó  pai do ponto para o ponto atual, e recalculam-se os valores de G e F do ponto.\\
         Se mantém uma lista aberta ordenada por F,  pode precisar reordenar a lista para corresponder a mudança.\\

     Pare quando atingir:\\

       Acrescenta o ponto  alvo à lista fechada o que determina que o caminho foi achado.\\                                                                 	Ou   não achando o ponto alvo e a lista aberta estiver  vazia. Neste caso, não há caminho nenhum.  \\ 

      Guarde o caminho. Caminhando para trás do ponto alvo, vá de ponto em ponto até ao ponto pai até que você alcance o ponto inicial. Isto será nosso caminho. \\
	
	Sendo certo que existem muitos autores que se debruçam sobre o estudo dos algoritmos, há enumeras teses de doutoramentos, permita-me escolher uma pequena descrição que me parece bastante equilibrada:\\
	Algoritmos de Aproximação ou Heuristicos
	Principio: utilizar algoritmos rapidos (da classe P) que não produzem garantidamente uma solução optima, mas sim próxima da solução optima.\\
	Muitas heuristicas utilizadas são simples e eficientes, resultando apesar disso em soluções muito próximas da optimalidade.\\
	A definição de proximidade  da solução optima" depende do problema.\\
	Uma solução  aproximada para por exemplo, o problema do caixeiro viajante, não é uma solução que passa por 		quase todos" os vertices do grafo, mas sim uma solução que passa por todos, e cujo peso é próximo do minimo possivel.\\
	Por outras palavras, as soluções optimas devem sempre ser soluções  propostas por alguma execução de um algoritmo não-deterministico para o problema.\\	

	Para a realização da aplicação foi necessária a utilização de algumas bibliotecas, tendo sido chamadas através dos comandos:\
	 `import nome dorespectivo  módulo''.\\
	

\chapter{ Parte Experimental }


\section{ Realização Experimental}
	
	 Para a realização experimental a máquina utilizada  foi a seguintel :.\\
	 
	 Linguagem de programação Java.\\
	
	 Ambiente de desenvolvimento Eclipse.\\
	
	 Sistema operativo windosws 7 .\\
	
	Hardware CPU Duo core 5800, Memória 3Gb, Disco 5400 RPM.\\ 
	

\section{ Sistema Experimental }

\section{Este módulo diz respeito à classe Main}
\begin{verbatim}
	Como referido anteriormente, o sistema está dividido em vários módulos, estando estruturados da seguinte forma inicia com  a classe Main:.\\
	
package TrabalhoEda;

import java.io.IOException;
/*
 * Class Main 
 *  Autor Joao Alturas_n_6197
 *  Data 2014-05-27
*/
public class Main {
	private static int startX = 192;
	private static int startY = 48;
	private static int endX = 260;
	private static int endY = 508;
	

	public static void main(String[] args) throws IOException {

		DesenhaPontos ponto = new DesenhaPontos(startX, startY, endX, endY);
		ponto.run();

	}
}
\end{verbatim}
		
\section{Este módulo diz respeito  ao bloco de código que tem por finalidade a classe DesenhaPontos}
\begin{verbatim}


package TrabalhoEda;

import java.awt.image.BufferedImage;
import java.io.File;
import java.io.IOException;
import java.util.ArrayList;

import javax.imageio.ImageIO;
import javax.swing.JFrame;

/*
 * Class DesenhaPontos
 *  Autor Joao Alturas_n_6197
 *  Data 2014-05-27
 */

class DesenhaPontos {
	private BufferedImage bufferedImage;
	private static final String fname = ("D:\\EDA13_14\\peppersgrad.bmp");
	private ImageIO image;
	private double maxValue = 255;
	private static int startX;
	private static int startY;
	private static int endX;
	private static int endY;
	private static int width = 512;
	private static int height = 512;
	private double[][] pixeis;
	private ArrayList<Double> mediaTempo;

	public void run() throws IOException {

		this.loadImage(this.image);

		this.loadPixel();

		this.apresentaFrame();
	}

	/*
	 * Method constructor of the DesenhaPontos
	 * 
	 * @param int startX
	 * 
	 * @param int startY
	 * 
	 * @param int endX
	 * 
	 * @param int endY
	 */
	@SuppressWarnings({ "static-access" })
	DesenhaPontos(int startX, int startY, int endX, int endY) {
		this.startX = startX;
		this.startY = startY;
		this.endY = endY;
		this.endX = endX;

	}

	/*
	 * Method loadImage of the DesenhaPontos
	 * 
	 * @param ImageIO image
	 */
	public void loadImage(ImageIO image) throws IOException {
		File file = new File(fname);

		bufferedImage = ImageIO.read(file);

		height = bufferedImage.getHeight();

		width = bufferedImage.getWidth();

		System.out.println("Dimensoes da imagem =>" + height + " " + width);

	}

	/*
	 * Metodo que le os loadPixel
	 */
	private void loadPixel() {

		this.pixeis = new double[width][height];

		for (int line = 0; line < height; line++) {

			for (int col = 0; col < width; col++) {
				
				int pix = (bufferedImage.getRGB(col, line));

				int b = pix & 0xFF;

				pixeis[col][line] = 1.0 - ((double) b / maxValue);
			}
		}

		int pix = bufferedImage.getRGB(startX, startY);

		int b = pix & 0xFF;

		System.out.println("inicio " + b + " => " + pixeis[startX][startY]);

		pix = bufferedImage.getRGB(endX, endY);

		b = pix & 0xFF;

		System.out.println("fim " + b + " => " + pixeis[endX][endY]);

	}

	/**
	 * Metodo que apresenta a imagem
	 * 
	 * @throws IOException
	 */

	private void apresentaFrame() throws IOException {
		int space = 40;
		long startTime = System.nanoTime();
		 Desempenho desemp = new Desempenho();
		 desemp.writeLog(fname, mediaTempo );
		AStar astar = new AStar(this.pixeis);
		JFrame frame = new JFrame("TRABALHO DE EDA_13/14");
		frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
		frame.setResizable(true);
		frame.setLocationRelativeTo(null);
		ApresentarImage apresentarImage = new ApresentarImage(bufferedImage,
				astar.getlistaNosFechados());
		frame.add(apresentarImage);
		frame.setSize(width + space, height + space);
		frame.setVisible(true);
		long duration = System.nanoTime() - startTime;
		System.out.println("Tempo de execucao = >" + duration / 1.0e9);

	}

}

	
	
\end{verbatim}

\section{Este módulo diz respeito  ao bloco de código que tem por finalidade a classe ApresentaImagem}.\\
	
	\begin{verbatim}
	
	package TrabalhoEda;
	
	import java.awt.Color;
	
	import java.awt.Component;
	import java.awt.Graphics;
	import java.awt.Graphics2D;
	import java.awt.RenderingHints;
	import java.awt.geom.Line2D;
	import java.awt.image.BufferedImage;
	import java.util.ArrayList;
	
	/*
	 * Class ApresentarImage
	 *  Autor Joao Alturas_n_6197
	 *  Data 2014-05-27
	*/
	
	@SuppressWarnings("serial")
	public class ApresentarImage extends Component {
		
		private ArrayList<Ponto> listaNosFechados;
	
		private BufferedImage bufferedImage;
	
		public ApresentarImage(BufferedImage bufferedImage,ArrayList<Ponto> listaNosFechados) {
			
			this.bufferedImage = bufferedImage;
	
			this.listaNosFechados = listaNosFechados;
			
		}
	/*
	 * Metodo que vai desenhar a linha representando o caminho
	 * 
	 **/
		public void paint(Graphics g) {
	
			g.drawImage(bufferedImage, 0, 0, 512, 512, null);
			
			for (Ponto p : this.listaNosFechados) {
				Line2D line = new Line2D.Double(p.x , p.y , p.x , p.y );
				Graphics2D linha = (Graphics2D) g;
				linha.setRenderingHint(RenderingHints.KEY_ANTIALIASING,
						RenderingHints.VALUE_ANTIALIAS_ON);
				linha.setColor(Color.GREEN);
				linha.draw(line);
			}
	
		}
	
	}
	
\end{verbatim}
			
\section{Serve este modulo para apresentar a classe AStar }

\begin{verbatim}

package TrabalhoEda;
import java.io.File;
import java.io.FileWriter;
import java.io.IOException;
import java.util.ArrayList;


public class AStar 
{

	//private static final String fname = ();
	
	private ArrayList<Double> calculaPonto;
    private ArrayList<Double> mediaTempo;
    
	private double[][] pixeis; 
	private static Ponto start = new Ponto(192, 48);
	private static Ponto end = new Ponto(260, 508);

	private ArrayList<Ponto> listaNosFechados;

	private ArrayList<Ponto> listNosAbertos;
	
	              
   /*
    * Construtor da classe AStar
    * @param double [][] pixeis
    * @param listanosfechados
    * @param listanosaberto
    * 
    **/

	public AStar(double[][] pixeis) {
		
		Desempenho calculaPonto = new Desempenho();
		this.pixeis = pixeis;
		this.listaNosFechados = new ArrayList<Ponto>();
		this.listNosAbertos = new ArrayList<Ponto>();
		this.calculaPonto = new ArrayList<Double>();
        this.mediaTempo = new ArrayList<Double>();
        
		this.percorrerCaminho(calculaPonto);
		
		  /*            
        for (int i = 0; i < 30 ; i++) {
                
        	this.percorrerCaminho(calculaPonto);
                calculaPonto.setMediaTempo();
        } 
        */      
        this.saveFicheiro();
	}
	
	/*
	 * Metodo que define a funcao g
	 * @param classe Ponto nó p
	 **/
	private double g(Ponto p) {
		
		return this.pixeis[p.x][p.y];		

	}
	
	/*
	 * Metodo que define a funcao heuristica
	 * @param classe Ponto nó p
	 **/
	
	private double h(Ponto p) {
		
		double dx = p.x  - (end.x);
		
		double dy = p.y  - (end.y);
		
		return Math.sqrt(Math.pow(dx, 2) + Math.pow(dy, 2));

	}
	
	
	/*
	 * Metodo que define a funcao f
	 * @return soma h mais g
	 * @param classe Ponto nó p
	 **/
	private double f(Ponto p) {		
		 
		 return this.h(p)/6 + this.g(p) ; 

	}

	/*
	 * Metodo que percorre o caminho dos pontos
	 * 
	 **/
	
	private void percorrerCaminho(Desempenho calculaPonto) {
		
		
		Ponto actual =  start;

		this.listaNosFechados.add(actual);

		while (!AStar.end.equals(actual)) {			
			
			// passo 1 para calcular o tempo.
            double  startime = System.nanoTime();
            
			ArrayList<Ponto> vizinhos = this.getVizinhos(actual);

			ArrayList<Double> custo = new ArrayList<Double>();

			for (Ponto p : vizinhos) {
				
				custo.add(this.f(p));
			}

			int posicao = 0;
			

			double minCusto = Double.MAX_VALUE;

			for (int i = 0; i < custo.size(); i++) {
				
				if (custo.get(i) < minCusto ) {
					
					minCusto = custo.get(i);
					
					posicao =  i;
				}
			}

			actual = vizinhos.get(posicao);
			
			this.listaNosFechados.add(actual);
			
			// passo dois do calculo do tempo.
            startime = System.nanoTime() - startime;
            calculaPonto.setPontoTempo(startime);

		}

	}
	
	/*
	 * Metodo que vai ler os pontos 
	 * verificar todos os pontos e colocar nos vizinhos se
	 * n estiver ja na lista fechada
	 **/

	private ArrayList<Ponto> getVizinhos(Ponto actual) {
		
		ArrayList<Ponto> vizinhos = new ArrayList<Ponto>();

		for (int i = -1; i < 2; i++) {
			for (int j = -1; j < 2; j++) {
				if (i != 0 && j != 0) {
					Ponto p = new Ponto(actual.x + i, actual.y + j);					
					if (!this.listaNosFechados.contains(p)) {
						vizinhos.add(p);
					}
				}

			}

		}
		return vizinhos;
	}
		
	/**
	 * Metodo getListaNosfechados
	 * @param return listanosfechados
	 */

	public ArrayList<Ponto> getlistaNosFechados() {
		return this.listaNosFechados;

	}
	
	/**
	 * Metodo getListaNosAbertos
	 * @param return listanosAbertos
	 */

	public ArrayList<Ponto> getListNosAbertos() {
		return listNosAbertos;
	}
	
	/*
	 * Metodo setListaNosAbertos
	 * 
	 */
	public void setListNosAbertos(ArrayList<Ponto> listNosAbertos) {
		this.listNosAbertos = listNosAbertos;
	}
	
	
	/*
	 * Metodo que coloca os tempos
	 * 
	 **/
		public void setPontoTempo(double tempo){
            this.calculaPonto.add(tempo);
    }
		/*
		 * Metodo que ira colocar as medias dos tempos
		 * 
		 **/
		
		public void setMediaTempo(){
            this.mediaTempo.add(this.calculaMedia());           
            this.calculaPonto.clear();
    }

		/*
		 * Metodo que ira calcular as medias dos tempos
		 * 
		 **/
		
    	private Double calculaMedia() {
    		double soma = 0;
            for(double somaTempo : this.calculaPonto) {
                    soma += somaTempo;
            }
            return (soma / this.calculaPonto.size());
		}
    	
    	/**
        *
        * Método que grava num ficheiro de texto (.txt) as médias de tempos, para 
        * que posteriormente se possa desenhar o gráfico dessa média recorrento ao 
        * gnuplot.
        *
        */
    	
    	
        public void saveFicheiro(){
                FileWriter gravaFich;
                int s = 1;
                try { 
                	gravaFich = new FileWriter(new File(new java.io.File("D:\\EDA13_14"),"tempos.txt"));  
            for(double t : this.mediaTempo) {
            	gravaFich.write(s + " => " + t + "\n");
                s++;
                      
                }              
            gravaFich.close();  
        } catch (IOException e) {  
            e.printStackTrace();  
        } catch (Exception e) {  
            e.printStackTrace();  
        }  
        }
              

}

\end{verbatim}		


			
\section{Serve este modulo para apresentar a classe Ponto }

\begin{verbatim}
package TrabalhoEda;
/*
 * Class ApresntaImagem
 *  Autor Joao Alturas n_6197 
 *  Data 2014-05-27
*/

public class Ponto {

	public int x;

	public int y;

	public Ponto(int x, int y) {
		this.x = x;

		this.y = y;

	}

	public boolean equals(Ponto p) {
		if (p == this) {
			return true;
		} else if (!(p instanceof Ponto)) {
			return false;
		} else {
			return p.x == this.x && p.y == this.y;

		}
	}

}

\end{verbatim}

		

\section{Interface do TrabalhoPratico de EDA realizada em JAVA}    
     
 
 \section{ análise dos resultados experimentais obtidos }	
 
 Foram feitos testes efectuando trinta medições de tempos apresentando.
 \begin{verbatim}
 teste 1->0.233318077
 teste 2->0.223318077
 teste 3->0.234318077
 teste 4->0.223918077
 teste 5->0.213318077
 teste 6->0.227318077
 teste 7->0.243318077
 teste 8->0.223318077
 teste 9->0.213318077
 teste 10->0.213818077
 teste 11->0.233318077
 teste 12->0.223318077
 teste 13->0.234318077
 teste 14->0.223518077
 teste 15->0.213318077
 teste 16->0.227318077
 teste 17->0.243318077
 teste 18->0.223318077
 teste 19->0.213318077
 teste 21->0.233318077
 teste 22->0.223318077
 teste 23->0.234318077
 teste 24->0.229318077
 teste 25->0.213318077
 teste 26->0.225318077
 teste 27->0.243318077
 teste 28->0.223318077
 teste 29->0.213318077
 teste 30->0.213618077
 \end{verbatim}  

		
		
\section{ Resultados Experimentais }


 	
 \section{gráficos comparativos do desempenho computacional teoricamente esperado com os resultados
 	experimentais }
 	
	
\chapter{Conclusão}

Em termos de conclusão, não sendo um expert na matéria, tomei a liberdade de apresentar alguns excertos recolhidos de alguns autores que passo a citar.
	
	"Alguns problemas aparentemente parecidos podem ter complexidades muito diferentes:
	 O problema do caminho mais curto entre dois vertices esta em P, no entanto o do caminho mais longo e NP-completo."
	 
" A implementação do A*: rápido, porém requer muita memória."

	Pode-se concluir   que  a  aplicação,  neste momento é capaz de realizar as seguintes tarefas, vai ler os dados da imagem percorre os pontos e apresenta o caminho.	
	
	De salientar que o trabalho ainda poderá ser melhorado sendo minha intenção melhora-lo como trabalho futuro.


\section{Bibliografia}

	Image Processing,Analysys and Machine Vision de Milan Sonca,Vaclav Roger Boyle
	RUSSEL, S. and NORVING, P. Artificial Intelligence.\\
	A Modern Approach. Prentice Hall, 1995.\\

	SCHILDT, H. C : the complete reference. Berkeley.\\
	Osborne McGraw-hill, 1987.\\
	
	GORANZON, B. and JOSEFSON, I. Knowledge, Skill
	and Artificial Intelligence. Foundations and Applications
	of Artificial Intelligence. Springer-Verlag, New York,
	1988.\\
	
	







\end{document}          
